#leetcode题目20：有效括号
#难度：简单
#时间复杂度：O(n)
#空间复杂度：O(n)
#方法：栈
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        lookup={
            "(":")",
            "[":"]",
            "{":"}"
        }
        for parenthesis in s:
            if parenthesis in lookup:
                stack.append(parenthesis) 
            elif len(stack)==0 or lookup[stack.pop()]!=parenthesis:
                return False
            
            
        return len(stack)==0



#测试数据
s="()"
#预期输出：True
solution=Solution()
print(solution.isValid(s))

s="()[]{}"
#预期输出：True
solution=Solution()
print(solution.isValid(s))

s="(]"
#预期输出：False
solution=Solution()
print(solution.isValid(s))

s="([)]"
#预期输出：False
solution=Solution()
print(solution.isValid(s))  

s=f"{[]}"
#预期输出：True
solution=Solution()
print(solution.isValid(s))



